МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ
КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ
ІНСТРУКЦІЯ
до лабораторної роботи № 2
з курсу “ Основи збору, передачі та обробки інформації”
для студентів базового напряму 6.1601
“Захист інформації”
Затверджено
на засiданнi кафедри
"Захист інформації"
Протокол N вiд . .2007 p.
Львів 2007
Дослідження кодоутворення та принципів побудови кодерів і декодерів циклічних кодів: інструкція до лабораторної роботи № 2 з курсів «Основи збору, передачі та обробки інформації» для студентів базового напрямку «Захист інформації» усіх форм навчання / Укл. М. В. Кіріанакі, В. В. Хома, В. І. Отенко, Я. Р. Совин. - Львів: НУЛП, 2007. - 9 с.
Укладачі: М. В. Кіріанакі, канд. техн. наук, доц., В. В. Хома, док. техн. наук, проф., В. І. Отенко, канд. техн. наук, доц., Я. Р. Совин, асист.
Відповідальний за випуск М. В.Кіріанакі, канд. техн. наук., доц.
Рецензенти: З. Р. Мичуда, канд. техн. наук., доц. О. В. Івахів, канд. техн. наук.. доп.
Складання і відлагодження схеми здійснено асист. каф. захисту інформації Совином Я. Р.
Мета роботи – ознайомлення з основами кодування і декодування цифрової інформації циклічними кодами і набуттю практичних навиків розробки функціональних схем кодерів і декодерів.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Циклічні коди (ЦК) є одними з найпростіших в реалізації та ефективних у забезпеченні високої завадостійкості і завдяки цьому широко використовуються не лише в телемеханіці, але і в обчислювальній техніці та зв’язку.
Для утворення циклічних кодів використовуються так звані неприведені поліноми Р(х), тобто многочлени, які не можна представити добутком поліномів нижчих степенів. Існує декілька різних способів кодування [1, 2].
Найпростіший спосіб утворення ЦК полягає у множенні многочлена G(х)1, який відповідає інформаційним ni розрядам первинного (безнадлишкового) коду, на утворюючий поліном Р(х). Такий спосіб легко реалізувати, але йому притаманний суттєвий недолік: одержані в результаті множення комбінації ЦК не містять в явному вигляд інформаційні розряди. Після виправлення помилок такі комбінації для виділення інформаційних символів доводиться ділити на утворюючий поліном.
Інший спосіб передбачає відведення під інформаційні ni , символи старших розрядів коду, а під контрольні nk = n - ni, символів молодших розрядів. Для утворення ЦК використовується така процедура. Многочлен G(х) який відповідає ni - розрядній кодовій комбінації (КК) первинного коду, множиться на . Ця операція еквівалентна приписуванню із боку молодших розрядів G(х) - nk нулів. Добуток G(х)* ділиться на утворюючий поліном Р(х). При цьому одержують частку Q(x) того ж степеня, що і G(х), та залишок R(x), який додається до G(х)* . Отже, КК циклічного коду буде визначатися як поліном
F(x) = G(х)* ( R(х) (1)
Оскільки степінь Р(х) вибирають nk, степінь залишку R(х), не перевищує nk - 1. В комбінації, що відповідає многочленові G(х)* , nk молодших розрядів нульові, і відповідно, операція додавання (1) рівносильна приписуванню R(x) до G(x) з боку молодших розряд. Очевидно, що R(х) має зміст контрольних розрядів ЦК. Таким чином, циклічний код можна будувати, приписуючи до кожної комбінації безнадлишкового коду G(х) залишок від ділення G(х)* на утворюючий поліном Р(х) коду.
Захисні можливості ЦК визначаються утворюючим поліномом Р(х), вибір якого має бути підпорядкований кільком правилам:
1. кількість ненульових членів Р(х) має бути не меншою від кодової віддалі d;
2.степінь полінома Р(х) не може бути меншим за nk (бажано, щоб він дорівнював nk);
3. довжина Р(х) має бути мінімальною.
ЦК, утворений поліномом P(x)=x + 1, забезпечує кодову віддаль d = 2 і збігається з кодом з захистом за паритетом, забезпечуючи виявлення не лише поодиноких помилок, але і довільної непарної ...